﻿namespace Jsl.FxCop
{
    using System;
    using System.Collections.Generic;
    using System.Linq;

    // TODO: Rewrite to remove recursion so we can traverse an arbitrary size tree.

    /// <summary>
    /// Does a depth first search of a graph.
    /// </summary>
    /// <typeparam name="TItem">The type of the item.</typeparam>
    public static class DepthFirstSearch<TItem>
    {
        #region Public Methods
        /// <summary>
        /// Searches starting at the specified item.
        /// </summary>
        /// <param name="firstItem">The first item.</param>
        /// <param name="itemVisitor">The item visitor.</param>
        /// <param name="getChildItems">Gets the child items.</param>
        /// <returns>The appropriate <see cref="SearchState"/>.</returns>
        public static SearchState Search(
            TItem firstItem,
            Func<TItem, SearchState> itemVisitor,
            Func<TItem, IEnumerable<TItem>> getChildItems)
        {
            return Search(new TItem[] { firstItem }, itemVisitor, getChildItems, null);
        }

        /// <summary>
        /// Searches the specified items.
        /// </summary>
        /// <param name="items">The items.</param>
        /// <param name="itemVisitor">The item visitor.</param>
        /// <param name="getChildItems">Gets the child items.</param>
        /// <returns>The appropriate <see cref="SearchState"/>.</returns>
        public static SearchState Search(
            IEnumerable<TItem> items,
            Func<TItem, SearchState> itemVisitor,
            Func<TItem, IEnumerable<TItem>> getChildItems)
        {
            return Search(items, itemVisitor, getChildItems, null);
        }

        /// <summary>
        /// Searches starting at the specified item.
        /// </summary>
        /// <param name="firstItem">The first item.</param>
        /// <param name="itemVisitor">The item visitor.</param>
        /// <param name="getChildItems">Gets the child items.</param>
        /// <param name="preventLoops"><c>true</c> if items should only be visited once.</param>
        /// <returns>The appropriate <see cref="SearchState"/>.</returns>
        public static SearchState Search(
            TItem firstItem,
            Func<TItem, SearchState> itemVisitor,
            Func<TItem, IEnumerable<TItem>> getChildItems,
            bool preventLoops)
        {
            return Search(new TItem[] { firstItem }, itemVisitor, getChildItems, preventLoops);
        }

        /// <summary>
        /// Searches the specified items.
        /// </summary>
        /// <param name="items">The items.</param>
        /// <param name="itemVisitor">The item visitor.</param>
        /// <param name="getChildItems">Gets the child items.</param>
        /// <param name="preventLoops"><c>true</c> if items should only be visited once.</param>
        /// <returns>The appropriate <see cref="SearchState"/>.</returns>
        public static SearchState Search(
            IEnumerable<TItem> items,
            Func<TItem, SearchState> itemVisitor,
            Func<TItem, IEnumerable<TItem>> getChildItems,
            bool preventLoops)
        {
            HashSet<TItem> visitedItems = preventLoops ? new HashSet<TItem>() : null;
            return Search(items, itemVisitor, getChildItems, visitedItems);
        }
        #endregion Public Methods

        #region Private Methods
        private static SearchState Search(
            IEnumerable<TItem> items,
            Func<TItem, SearchState> itemVisitor,
            Func<TItem, IEnumerable<TItem>> getChildItems,
            HashSet<TItem> visitedItems)
        {
            // Get the list of items to visit. Throw out any items we have already visited.
            IEnumerable<TItem> itemsToVisit;
            if (visitedItems == null)
            {
                itemsToVisit = items;
            }
            else
            {
                itemsToVisit = items.Where(item => !visitedItems.Contains(item));
            }

            // Walk through each item in the collection.
            foreach (TItem item in itemsToVisit)
            {
                // Add this item to the list we've already visited.
                if (visitedItems != null)
                {
                    visitedItems.Add(item);
                }

                // Visit the item.
                switch (itemVisitor(item))
                {
                    case SearchState.ContinueSearch:
                        // Search all the descendants. Exit if any return StopSearch.
                        var childSearchState = Search(
                            getChildItems(item),
                            itemVisitor,
                            getChildItems,
                            visitedItems);
                        if (childSearchState == SearchState.StopSearch)
                        {
                            return SearchState.StopSearch;
                        }

                        break;

                    case SearchState.SkipDescendants:
                        break;

                    case SearchState.StopSearch:
                        return SearchState.StopSearch;
                }
            }

            return SearchState.ContinueSearch;
        }
        #endregion Private Methods
    }
}